import java.util.ArrayList;


public class BinaryTree<T extends Comparable<T>> {
	private TreeNode<T> root;
	
	BinaryTree (TreeNode<T> r){
		root = r;
	}
	BinaryTree(){
		root = null;
	}
	public TreeNode<T> getRoot(){
		return root;
	}
	public BinaryTree<T> setRoot(TreeNode<T> r){
		root = r;
		return this;
	}
	public boolean isEmpty(){
		return root==null;
	}
	public String inOrder(){
		return inOrder(root);
	}
	public String postOrder(){
		return postOrder(root);
	}
	public String preOrder(){
		return preOrder(root);
	}
	
	public String levelOrder(){
		String s="";
		ArrayList<String> a = new ArrayList<String>();
		a = levelOrder(root,0,a);
		for (int i=0; i<a.size();i++)
			s += a.get(i);
		return s;
	}

	private ArrayList<String> levelOrder(TreeNode<T> r, int i, ArrayList<String> a){
		String s;
		if (r != null){
			while(i>=a.size())
				a.add("");
			s = a.get(i) + r.toString()+ " ";
			a.remove(i);
			a.add(i, s);
			levelOrder(r.getLeft(),  i+1,a);
			levelOrder(r.getRight(), i+1,a);
			
		}
		return a;
	}
	private String inOrder (TreeNode<T> r){
		String s= "";
		if(r != null){
			s += inOrder(r.getLeft());
			s += r.toString()+" ";
			s += inOrder(r.getRight());
		}
		return s;
	}
	private String postOrder (TreeNode<T> r){
		String s= "";
		if(r != null){
			s += postOrder(r.getLeft());
			s += postOrder(r.getRight());
			s += r.toString()+" ";
		}
		return s;
	}
	private String preOrder (TreeNode<T> r){
		String s= "";
		if(r != null){
			s += r.toString()+" ";
			s += preOrder(r.getLeft());
			s += preOrder(r.getRight());
		}
		return s;
	}
	public TreeNode<T> insert(T o){
		return insert(new TreeNode<T>(o));
	}
	
	public TreeNode<T> insert(TreeNode<T> r) {
		if (this.getRoot() != null)
			return insert(r, this.getRoot());
		else
			this.setRoot(r);
		return this.getRoot();
	}
	
	public ArrayList<TreeNode<T>> inOrderList(){
		return inOrderList(root);
	}
	private ArrayList<TreeNode<T>> inOrderList(TreeNode<T> r){
		ArrayList<TreeNode<T>> ar = new ArrayList<TreeNode<T>>();

		if (r != null){
		ar.addAll(inOrderList(r.getLeft()));
		ar.add(r);
		ar.addAll(inOrderList(r.getRight()));
		}
		return ar;
		
		
	}
	public int size(){
		return size(0, this.getRoot());
	}
	
	public int height(){
		return height(-1,this.getRoot());
	}
	public int leaves(){
		return leaves(0,this.getRoot());
	}
	private int leaves(int i, TreeNode<T> r){
		if (r!= null){
			if (r.getLeft()== null && r.getRight() == null)
				i++;
			else
				i= leaves(i,r.getLeft());
				i= leaves(i,r.getRight());
		}
		return i;
	}
	
	private int height(int i, TreeNode<T> r){
		int j=0;
		int k=0;
		if (r != null){
			i++;
			j= height(0, r.getLeft());
			k= height(0, r.getRight());
			i += (k > j) ? k : j;
		}
		return i;
	}
	private int size(int i, TreeNode<T> r){
		if(r!= null){
			i++;
			i = size(i, r.getRight());
			i = size(i, r.getLeft());
		}
		return i;
	}
	
	
	private TreeNode<T> insert (TreeNode<T> key, TreeNode<T> node){
		if(key != null){
			if (key.getKey().compareTo(node.getKey()) < 0)
				if (node.getLeft() == null)
					return node.setLeft(key);
				else
					return insert(key,node.getLeft());
			else
				if (key.getKey().compareTo(node.getKey()) > 0)
					if(node.getRight() == null)
						return node.setRight(key);
					else
						return insert(key,node.getRight());
			
		}
		throw new java.util.NoSuchElementException();  
	}
}
